Log(coins)-sized proofs of inclusion and exclusion for RSA accumulators
m0t0k1ch1.icon fragment が大量に存在する場合にそれらに関する proof of inclusion/exclusion を効率的に行うことができる RSA accumulator について、その概要を把握する
m0t0k1ch1.icon 途中から出てくる Merkle forest が曲者なので注意
---.icon
In a naive RSA Plasma Cash implementation, each coin is assigned a unique prime number as a coin ID, and the RSA accumulator update for that block includes the coin ID for each coin that was spent. For a user with a width-$ nfragment, a proof of inclusion has size$ O(N)and a proof of exclusion has size$ O(N), and the operator has$ O(N)overhead, making this scheme ineffective if we want to achieve very fine denominations.
素朴な RSA Plasma Cash においては、各コインには一意な素数がコイン ID として割り当てられる。ブロック生成のための RSA accumulator の更新には、使用された各コインのコイン ID が含まれる。幅$ nの fragment を有するユーザーの場合、proof of inclusion のサイズは$ O(N)であり、proof of exclusion のサイズも$ O(N)である。このとき、オペレーターには$ O(N)のオーバーヘッドが生じる。また、とても細かい単位でのコイン管理を実現する場合、このスキームは非効率的である。
We’ll start off with a scheme that cuts down proofs of exclusion to size$ O(\log{(N)})at the cost of increasing proofs of inclusion for one coin to$ O(\log{(N)})(a proof for$ Ncoins only increases by a factor of two). We generate a tree of primes associated with indices of coins and subsets of indices corresponding to nodes in a binary tree, for example for 4 coins as follows:
1 コインあたりの proof of inclusion のサイズを$ O(\log{(N)})まで増やす（$ N個のコインの proof のサイズは 2 倍になるだけで済む）こととひきかえに、proof of exclusion のサイズを$ O(\log{(N)})まで削減するスキームから出発する。コインのインデックスと紐づいた素数で tree をつくる。このとき、インデックスのサブセットはバイナリツリーのノードに対応する。例えば、4 コインで考えると以下のようになる。
https://gyazo.com/b8fbf692fec777d4957b9dfc4fdc97e6
To include coin 7, you would set$ A' = A^{2 * 3 * 7}. To include both coins 13 and 17, you would set$ A' = A^{2 * 5 * 13 * 17}, to include both 11 and 13 you would set$ A' = A^{2 * 3 * 5 * 11 * 13}. To prove membership of eg. coin 17, you would need to prove that$ 2 * 5 * 17is part of the accumulator (ie. $ A'is a known power of$ A^{2 * 5 * 17}).
コイン$ 7を含めるときは$ A' = A^{2 * 3 * 7}となる。コイン$ 13と$ 17を両方含めるときは$ A' = A^{2 * 5 * 13 * 17}となる。コイン$ 11と$ 13を両方含めるときは$ A' = A^{2 * 3 * 5 * 11 * 13}となる。例えば、コイン$ 17の membership を証明するためには、$ 2 * 5 * 17が accumulator の一部である（すなわち、$ A'が$ A^{2 * 5 * 17}の累乗である）ことを証明する必要がある。
m0t0k1ch1.icon こういうルールで accumulator に値を追加していったら、proof of inclusion はこうなるよねという話
To prove non-membership of an aligned slice (a slice which corresponds exactly to a subtree), only a single proof of non-membership, eg. of$ 3, is required. For arbitrary slices, you can construct a proof that batches together$ \log{(n)}proofs of subtrees; in general, any slice$ \lbrack a, b \rbrackcan be decomposed into$ \log{(b - a)}adjacent aligned slices. For example, to prove that 11, 13 and 17 are all not part of the accumulator, you would need to prove that 11 and 5 are both excluded, and so you need simply prove that$ \log_A{(A')} \mod{55}is a value that is not a multiple of 5 or 11. Hence, proving non-membership of a range can now be done compactly. However, proving membership of a range unfortunately still requires a batched proof of all of the individual coins.
aligned slice（厳密に subtree と対応する部分）の non-membership を証明する場合は、proof of non-membership（例えば$ 3）が 1 つあればよい。任意の slice について、$ \log{(n)}個の subtree の proof をまとめた proof を構築できる。一般的には、任意の slice$ \lbrack a, b \rbrackは$ \log{(b - a)}個の隣接した aligned slice に分解できる。例えば、$ 11と$ 13と$ 17が全て accumulator の一部でないことを証明する場合、$ 5と$ 11がともに accumulator の一部でないことを証明すればよい。すなわち、単純に$ log_A{A'} \mod{55}が$ 5もしくは$ 11の倍数でないことを示せばよい。このようにすれば、ある範囲の non-membership の証明を簡潔に行うことができる。しかし、残念なことに、ある範囲の membership の証明は、全てのコインに関するまとまった proof が必要である。
m0t0k1ch1.icon まだ上の図の話
m0t0k1ch1.icon 上記のルールで accumulator に値を追加していくとすると、例えば$ 5が accumulator に含まれない場合、$ 13と$ 17の両方が accumulator に含まれないことは自明（tree の構造的に、$ 5が含まれるのは$ 13と$ 17のどちらかもしくは両方が含まれるときだけ）なので、$ 13と$ 17の non-membership を証明したい場合は$ 5の non-membership を証明するだけで十分、ということになる
m0t0k1ch1.icon proof のサイズのオーダーに関しては理論が厳密に正しいかは分からない
m0t0k1ch1.icon この話が正しいとすると、できるだけ自分のコインの fragment が厳密な subtree としてまとまっていた方が効率的になるはずなので、デフラグの話とも関連してくるのだと思う
m0t0k1ch1.icon ここまでを「提案 1」、これ以降を「提案 2」と呼称することとする
We can deal with this problem by extending the scheme further, making a Merkle forest instead of a tree:
さらにスキームを拡張することで、この問題に対処することができる。tree ではなく、以下のような Merkle forest を構築する。
https://gyazo.com/37fde12ed6b3b754884fd10e6d571c90
To prove membership of a single aligned slice, you now need to prove several things:
ある 1 つの aligned slice の membership を証明したい場合、以下を証明する必要がある。
・The leaf value corresponding to the subtree is included, as are all of its ancestors up to that root.
・The leaf values in any higher tree in the forest are not included.
・The value corresponding to the subtree is not included in any lower tree in the forest.
subtree に対応する leaf の値が、root までに存在するその全ての先祖と同様、含まれていること
forest 内のより高い tree に leaf の値が含まれていないこと
subtree に対応する値が、forest 内のより低い tree に含まれていないこと
m0t0k1ch1.icon subtree って言ってるのは、membership を証明したい aligned slice のことだと思う
m0t0k1ch1.icon この文章だけで理解するのは難しいので、下の図を見てから戻ってきた方がよい
This is best illustrated by example. Suppose we want to prove membership of coin 1 (ie. the second coin from the left). Values for which we prove membership are colored green, and values for which we prove non-membership are colored red:
これは、例えば以下のように表せる。コイン$ 1（左から 2 番目のコイン）の membership を証明したい場合、緑色の値の membership を証明し、赤色の値の non-membership を証明する。
https://gyazo.com/9e8728a617a798476b9a4d5cf492dc9b
m0t0k1ch1.icon コイン$ 1は$ 23
m0t0k1ch1.icon 読み進める前に、「ある slice を accumulator に追加する場合、実際に accumulator はどのような演算をするか」という観点でいくつか具体例を考え、提案 2 のルールを直感的にイメージできるようにする
slice$ \lbrack 0 \rbrack（$ 19）を追加する：$ A' = A^{5 * 13 * 19}
single element slice
slice$ \lbrack 0 \ldots 1 \rbrack（$ 19と$ 23）を追加する：$ A' = A^{3 * 7}
サイズ$ 2^1の aligned slice
slice$ \lbrack 0 \ldots 2 \rbrack（$ 19と$ 23と$ 29）を追加する：$ A' = A^{3 * 5 * 7 * 17 * 29}
一部がサイズ$ 2^1の aligned slice な slice
slice$ \lbrack 0 \ldots 3 \rbrack（$ 19と$ 23と$ 29と$ 31）を追加する：$ A' = A^2
サイズ$ 2^2の aligned slice
m0t0k1ch1.icon ある slice を accumulator に追加するときの考え方は以下のようなイメージ
まずは提案 1 と同様に考える
以降は「aligned slice があれば上位の tree を利用する」を繰り返す
Now, suppose we want to prove inclusion of the aligned slice containing coin 0 and coin 1:
ここで、コイン$ 0と$ 1を含んだ aligned slice の membership を証明したい場合は以下のようになる。
https://gyazo.com/2a2ea63d651141aba813bceb2a9ccf36
m0t0k1ch1.icon コイン$ 0は$ 19、コイン$ 1は$ 23
m0t0k1ch1.icon 前述した通り、accumulator に$ 19と$ 23を追加する場合は$ A' = A^{3 * 7}という演算が行われている
m0t0k1ch1.icon よって、まずは$ 3と$ 7の membership を証明する必要がある（aligned slice ではないので単純に考える）
m0t0k1ch1.icon $ 2は、accumulator に$ 19と$ 23と$ 29と$ 31が追加されたときにのみ含まれる数字なので、ここでは$ 2の non-membership を証明する必要がある
m0t0k1ch1.icon $ 13は、accumulator に$ 19と$ 23のどちらかが追加されたときにのみ含まれる数字なので、ここでは$ 13の non-membership を証明する必要がある
The general principle is that there are separate trees that are used to prove membership of an aligned slice at each$ 2^ksize level, and this proof of membership includes a proof that aligned slices intersecting with that slice at higher or lower levels are not included.
一般原則として、サイズ$ 2^kの aligned slice の membership を証明するために使われる複数の tree が存在し、この proof of membership は、より高いもしくはより低い位置にその slice と交わる aligned slice が含まれていないという proof を含む。
m0t0k1ch1.icon 上記の例と照らし合わせると以下のようになる
「サイズ$ 2^kの aligned slice（その slice）」は「slice$ \lbrack 0 \ldots 1 \rbrack（$ 19と$ 23）」のこと（自明だが、$ k = 1）
「より高い位置にその slice と交わる aligned slice が含まれていないという proof」は「$ 2の proof of non-membership」のこと
「より低い位置にその slice と交わる aligned slice が含まれていないという proof」は「$ 13の proof of non-membership」のこと
Now, to prove that a given aligned slice is not included, we make a proof as follows (using coins 0 and 1 as an example):
任意の aligned slice が含まれていないことを証明する場合、以下のような proof を生成すればよい（例の如く、コイン$ 0と$ 1について考える）。
https://gyazo.com/c7b9d093baf6500783df21a91b7622db
This proves that:
これは以下を証明する。
1. The aligned slice$ \lbrack 0 \ldots 3 \rbrackcannot be included (as that would require including the prime$ 2, which we prove is excluded)
2. The aligned slice$ \lbrack 0 \ldots 1 \rbrackcannot be included (as that would require including the prime$ 7)
3. The individual coins$ 0or$ 1cannot be included (as either of those proofs would require including the prime$ 13)
1. aligned slice$ \lbrack 0 \ldots 3 \rbrackが含まれていないこと（この aligned slice が含まれる場合、$ 2が含まれるはずだから）
2. aligned slice$ \lbrack 0 \ldots 1 \rbrackが含まれていないこと（この aligned slice が含まれる場合、$ 7が含まれるはずだから）
3. コイン$ 0と$ 1のどちらかだけが含まれていないこと（どちらかだけが含まれる場合、$ 13が含まれるはずだから）
All of these proofs are of size$ \log{(n)}for$ ntotal coins, and this includes both cost of verification and transmission and cost of construction. If all transactions ever only touched two-coin aligned slices, no one will ever need to do any calculations using the primes$ 19, 23, 29or$ 31.
$ n個のコインに対して、これら全ての proof のサイズは$ \log{(n)}となる。また、これは検証・伝達コストと構築コストの両方を含む。全てのトランザクションが 2 コインから成る aligned slice にしか触れない場合、誰も素数$ 19, 23, 29, 31を使った計算をする必要はない。
m0t0k1ch1.icon 「これは検証・伝達コストと構築コストの両方を含む」ってどういうこと？
If a Plasma Cash implementation wishes to use a very large number of coins (eg.$ 2^{50}coins), then this is a very helpful feature. However, how do we assign primes to that many coins? Ideally, we want primes that are as small as possible, as these are more efficient to generate proofs for.
Plasma Cash の実装が大量のコイン（例えば$ 2^{50}個）を扱う場合、これは非常に有用な特徴である。しかし、そのような大量のコインにどのようにして素数を割り当てればよいだろうか？理想としては、より効率的に proof を生成するために、素数はできるだけ小さくしたい。
One solution is to come up with a function that deterministically generates a prime on-demand for any given index. Given what we know about prime gaps, simply mapping$ xto the first prime above$ 25000 * xshould be sufficient. The problem is that deterministic 100% effective primality tests have a high runtime, making them difficult to use on-chain. A simpler approach (thanks @ldct) is to simply do one round of precalculation which generates the list of the first$ 2^{40}prime numbers and stores them in a Merkle tree; any use of the primes on-chain would need to be combined with a Merkle branch. Any client could check the precalculation locally. 解決策の 1 つは、任意のインデックスに対して、要求に応じて決定論的に素数を生成する関数を考え出すこと。素数ギャップ について我々が知っていることを加味すると、単純に$ xを$ 25000 * xを上回る最初の素数にマッピングするだけで十分である。 問題は 素数判定 の実行時間が長く、オンチェーンで使用するのが困難であるという点である。よりシンプルなアプローチは、単純に$ 2^{40}個の素数リストを事前に計算して生成し、それを Merkle tree として保持することである。このとき、オンチェーンでの素数の使用は Merkle branch と組み合わせる必要があるだろう。また、クライアントは事前計算をローカルで確認することができる。 m0t0k1ch1.icon 「オンチェーンでの素数の使用は Merkle branch と組み合わせる必要があるだろう」をもう少し噛み砕くと、「オンチェーン上である数を素数として使用するには、オンチェーン上で素数であることを証明する必要があるので、事前に計算された素数 Merkle tree にその数が含まれていることを Merkle branch によって証明しながら処理を行う必要があるだろう」ってこと？
m0t0k1ch1.icon オンチェーンで保持するのは Merkle root のみで OK？